import java.util.Arrays;

public class Solution76 {
    /**
     * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
     *
     * 示例：
     *
     * 输入: S = "ADOBECODEBANC", T = "ABC"
     * 输出: "BANC"
     */
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length()){
            return "";
        }
        int[] needs = new int[128];
        int[] window = new int[128];
        for (int i = 0; i<t.length(); i++) {
            needs[t.charAt(i)]++;
        }

        int l = 0;
        int r = 0;

        String res = "";
        int count = 0;
        int min = s.length() + 1;

        while (r < s.length()){
            char c = s.charAt(r);
            window[c]++;
            if (needs[c] > 0 && needs[c] >= window[c]){
                count++;
            }

            while (count == t.length()){
                c = s.charAt(l);
                if (needs[c] > 0 && needs[c] >= window[c]){
                    count--;
                }
                if (r - l + 1 < min) {
                    min = r - l + 1;
                    res = s.substring(l, r + 1);
                }
                window[c]--;
                l++;
            }
            r++;
        }
        return res;
    }

}
